package 剑指offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class p32_II从上到下打印二叉树 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new LinkedList<>(); // 使用链表比顺序表更快，但是链表的add直接进行尾插更高效，而顺序表的add要进行当前数组元素的比较
        if (root==null) {
            return res;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size=queue.size();// 记录当前队列中的元素个数，是解决按层记录的关键！！！！！

            List<Integer> tmp=new ArrayList<>();
            for (int i = 0; i <size; i++) {
                TreeNode poll=queue.poll();

                if (poll.left!=null) {
                    queue.add(poll.left);
                }
                if (poll.right!=null) {
                    queue.add(poll.right);
                }

                tmp.add(poll.val);
            }
            res.add(tmp);
        }

        return res;
    }
}
